from math import ceil


class Solution:
    def tilingRectangle(self, n: int, m: int) -> int:
        if n == 0 or m == 0:
            return 0
        if n == m:
            return 1
        if n == 1 or m == 1:
            return (n + m) - 1

        if n > m:
            n, m = m, n

        if m % n == 0:
            return m // n

        # [剪枝1] 当前长边长度超过短边的2倍，那么先放置一块短边边长尺寸的地砖
        if m > n + n:
            return 1 + self.tilingRectangle(n, m - n)

        # 此时有：n < m < n + n

        # 策略1:第一块地砖为短边边长长
        ans = 1 + self.tilingRectangle(n, m - n)

        # 策略2:第一块地砖比短边更短
        # 有3种情况
        # 2 2 2 2 4 4 4 4       2 2 2 2 2 2 4 4       2 2 2 2 2 4 4 4
        # 2 2 2 2 5 3 3 3       2 2 2 2 2 2 4 4       2 2 2 2 2 4 4 4
        # 1 1 1 1 1 3 3 3       1 1 1 1 1 5 4 4       1 1 1 1 1 3 3 3
        # 1 1 1 1 1 3 3 3       1 1 1 1 1 5 4 4       1 1 1 1 1 3 3 3
        # 1 1 1 1 1 3 3 3       1 1 1 1 1 3 3 3       1 1 1 1 1 3 3 3
        # 1 1 1 1 1 3 3 3       1 1 1 1 1 3 3 3       1 1 1 1 1 3 3 3
        # 1 1 1 1 1 3 3 3       1 1 1 1 1 3 3 3       1 1 1 1 1 3 3 3

        # [剪枝2] 砖缝里的砖应该比第一块砖小 -> 第一块砖应大于等于窄边和宽边的一半 （否则可以调换它们）
        for s0 in range(ceil(m / 2), n):
            s1, s2 = n - s0, m - s0  # s1=窄边剩余宽度;s2=宽边剩余宽度
            n1, n2 = s0 // s1, s0 // s2  # n1=窄边剩余宽度不超出s0所需的砖块数,n2=宽边剩余宽度不超出s0所需的砖块数
            s3, s4 = s1 * n1, s2 * n2  # s3=窄边放上n1块砖的长度,s4=宽边放上n2块砖的长度

            # [剪枝3] 铺上第一块地砖后，窄边和长边的缝隙里补充的砖已经超过之前的最优解
            if n1 + n2 + 1 >= ans:
                continue

            # print("第1块:", s0, [s1, s3], [s2, s4], "->", 1 + n2 + n2)

            # 第1种情况
            if s3 + s1 <= m:
                s5, s6 = m - s3 - s1, n - s4  # 右上角部分的长和宽（策略2中的4区域）
                s7, s8 = s3 + s1 - s0, s0 - s4  # 中间部分的长和宽（策略2中的5区域）
                # print("第1种情况:", 1 + (n1 + 1) + n2, [s5, s6], [s7, s8])
                ans = min(ans, 1 + (n1 + 1) + n2 + self.tilingRectangle(s5, s6) + self.tilingRectangle(s7, s8))

            # 第2种情况
            if s4 + s2 <= n:
                s5, s6 = n - s4 - s2, m - s3  # 右上角部分的长和宽（策略2中的4区域）
                s7, s8 = s4 + s2 - s0, s0 - s3  # 中间部分的长和宽（策略2中的5区域）
                # print("第2种情况:", 1 + n1 + (n2 + 1), [s5, s6], [s7, s8])
                ans = min(ans, 1 + n1 + (n2 + 1) + self.tilingRectangle(s5, s6) + self.tilingRectangle(s7, s8))

            # 第3种情况
            if s3 == s0:
                # print("第3种情况:", 1 + n1 + n2, [s2, n - s4])
                ans = min(ans, 1 + n1 + n2 + self.tilingRectangle(s2, n - s4))
            if s4 == s0:
                # print("第3种情况:", 1 + n1 + n2, [s1, n - s3])
                ans = min(ans, 1 + n1 + n2 + self.tilingRectangle(s1, n - s3))

        return ans


if __name__ == "__main__":
    print(Solution().tilingRectangle(2, 3))  # 3
    print(Solution().tilingRectangle(5, 8))  # 5
    print(Solution().tilingRectangle(11, 13))  # 6

    # 测试用例35/38
    print(Solution().tilingRectangle(7, 6))  # 5

    # 测试用例34/38
    print(Solution().tilingRectangle(10, 9))  # 6

    # 测试用例37/38
    print(Solution().tilingRectangle(11, 10))  # 6
